package leetcode.search;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 在给定的二维二进制数组A中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

 现在，我们可以将0变为1，以使两座岛连接起来，变成一座岛。

 返回必须翻转的0 的最小数目。（可以保证答案至少是 1 。）
 */
public class ShortestBridge934 {

    public int shortestBridge(int[][] grid) {
        int [] dir = new int[]{-1,0,1,0,-1};

        int m = grid.length;
        int n = grid[0].length;
        LinkedList<int[]> queue = new LinkedList<int[]>();
        boolean find =false;
        for (int i = 0; i < m; i++) {//找到第一个岛屿，并标记成2
            if(find) break;
            for (int j = 0; j < n; j++) {
                    if(grid[i][j]==1){
                        find = true;
                        dfs(queue,grid,i,j,m,n);
                        break;
                    }
            }
        }

        int level = 0;
        while (!queue.isEmpty()){
            level++;
            int size = queue.size();
            while (size>0){//这一层的
                size--;
                int[] point = queue.poll();
                for (int i = 0; i < dir.length-1; i++) {//这个点所联通的点
                    int x = point[0]+dir[i];
                    int y = point[1]+dir[i+1];

                    if(x<0 || x>=m || y<0 ||y>=n )
                        continue;

                    if(grid[x][y]==1)//达到目的地
                        return level;

                    if(grid[x][y]==2)//访问过了
                        continue;

                    queue.add(new int[]{x,y});
                    grid[x][y] = 2;
                }
            }
        }
        return  -1;
    }

    public void dfs(LinkedList<int[]> que,int [][]grid,int x,int y,int m, int n){
            if(x<0 || x>=m || y<0 ||y>=n || grid[x][y]==2)
                return;

            if(grid[x][y]==0){
                que.add(new int[]{x,y});
                return;
            }

            grid[x][y]=2;
            dfs(que,grid,x+1,y,m,n);
            dfs(que,grid,x-1,y,m,n);
            dfs(que,grid,x,y+1,m,n);
            dfs(que,grid,x,y-1,m,n);
    }
}